package interview.loop;

import java.util.ArrayList;
import java.util.Arrays;

import interview.common.Node;
import interview.recursion.LinkedListCreator;

public class LinkedListDeletor
{
	// 定义一个函数
	public Node deleteIfEquals(Node head, int value)
	{
		/*
		 * 如果头结点=我们要删除的value，头结点就要删掉，所以头结点要往后移。 所以删除的结果，头结点不一定是原先的头结点(Node head)。
		 * 所以需要返回一个头结点——>新的头结点。
		 */

		// 特殊处理：处理头结点
		// 封神操作：把if改成while!
		while (head != null && head.getValue() == value)// 头结点=要删除的value
		{
			head = head.getNext();// 头结点后移一个
		} // 跳出循环:head == null

		if (head == null)
		{
			return null;
		}

		// 处理一般情况
		Node prev = head;// 保证prev是最后一个结点
		// Loop invariant: list nodes from head up to prev has been processed. (Nodes
		// with values equal to value deleted)
		while (prev.getNext() != null)
		{
			// 处理prev.getNext() == null

			// prev的next结点是不是我们要删除的值？是，就删除
			if (prev.getNext().getValue() == value)// 3——>2
			{
				// delet it
				prev.setNext(prev.getNext().getNext());// 把指针跳过去：3——>5
			} else
			{// 不是，往后移一个
				prev = prev.getNext();
			}
		}
		return head;
	}

	public static void main(String[] args)
	{
		LinkedListCreator creator = new LinkedListCreator();
		LinkedListDeletor deletor = new LinkedListDeletor();

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(1, 2, 3, 2, 5)), 2));

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(1, 2, 3, 2, 2)), 2));

		// 删除头结点
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(1, 2, 3, 2, 2)), 1));

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2, 2, 3, 2, 2)), 2));

		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2, 2, 2, 2, 2)), 2));

		// 单点
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2)), 2));
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(Arrays.asList(2)), 1));

		// 空集
		Node.printLinkedList(deletor.deleteIfEquals(creator.creatLinkedList(new ArrayList<Integer>()), 1));

		// 打印linked list，见Node.java
	}

}
